package 力扣题库;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class p77组合 {

    public List<List<Integer>> combine(int n, int k) {
        //回溯算法
        List<List<Integer>> res=new ArrayList<>();
        Deque<Integer> path=new ArrayDeque<>();

        dfs(n,k,1,path,res);
        return res;
    }

    private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        //递归出口
        if (path.size()==k) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = begin; i <=n; i++) {
            path.addLast(i);
            //开始递归
            dfs(n,k,i+1,path,res);

            //递归结束后，进行回溯
            path.removeLast();
        }
    }
}
